class Solution {
    /*
        动态规划，注意两个情况：
        1、d[i]的最大值为4000，如何设为Integer.MAX_VALUE会越界
        2、注意d[0] = 0;
    */
    public int coinChange(int[] coins, int amount) {
        int[] d = new int[amount+1];
        for(int i=0; i<=amount; i++)
            d[i] = 9999;
        for(int i=0; i<coins.length; i++){
            if( coins[i]<=amount ) 
                d[ coins[i] ] = 1;
        }
        d[0] = 0;
        for(int money=1; money<=amount; money++){
            for(int i=0; i<coins.length; i++){
                if( money-coins[i]>0 ){
                    d[ money ] = Math.min(d[money],d[ money-coins[i] ]+1);
                }
            }
        }
        return d[amount]==9999 ? -1 : d[amount];
    }
}
class Solution {
    /*
        官方答案
    */
    public int coinChange(int[] coins, int amount) {
        int max = amount+1;
        int[] d = new int[max];
        Arrays.fill(d,max);
        d[0] = 0;
        for(int money=1; money<=amount; money++){
            for(int i=0; i<coins.length; i++){
                if( money-coins[i]>=0 ){
                    d[ money ] = Math.min(d[money],d[ money-coins[i] ]+1);
                }
            }
        }
        return d[amount]==max ? -1 : d[amount];
    }
}